﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Sorts
{
    class ShellSort
    {
        public static void Sort(int[] items)
        {
            var h = 1;
            while (h <= (items.Length - 1) / 3)
            {
                h = 3 * h + 1;
            }

            // 对间隔为 h 的元素进行排序，如：（0，h，2h）、（1，h + 1，2h + 1）。
            while (h >= 1)
            {
                // 将 outer 对应的元素按照插入排序的算法（间隔为 h）插入到指定的位置。
                // h 之前的元素都是已排序的。
                for (var outer = h; outer < items.Length; outer++)
                {
                    var temp = items[outer];
                    var inner = outer;
                    while (inner >= h && items[inner - h] > temp) // 闲了得思考一下：不变量和 while。
                    {
                        items[inner] = items[inner - h];
                        inner = inner - h;
                    }
                    items[inner] = temp;
                }
                h = (h - 1) / 3;
            }
        }
    }
}
